/*************************************************************************
 * File Name:    Roman_to_Integer.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: 2013/11/9 10:48:42
 * 
 * Description:  
 |------------------------------------------------------------------------
 | Problem: Roman to Integer
 | Given a roman numeral, convert it to an integer.
 |
 | Input is guaranteed to be within the range from 1 to 3999.
 |------------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>

using namespace std;

class Solution {
public:
    int romanToInt(string s)
    {
        const string roman[] = {"I", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD", "D", "CM", "M"};
        const int integer[] =  { 1,    4,   5,    9,   10,  40,   50,  90,   100, 400, 500, 900,  1000};
        int ans = 0;
        
        for (size_t i = sizeof(integer) / sizeof(integer[0]); i > 0; --i) {
            while (s.size() >= roman[i - 1].size() && s.substr(0, roman[i - 1].size()) == roman[i - 1]) {
                ans += integer[i - 1];
                s = s.substr(roman[i - 1].size());
            }
        }
        return ans;
    }
};

int
main(int argc, char *argv[])
{
    Solution sol;

    cout << sol.romanToInt("DCXXI") << endl;

    return 0;
}
